package dp;

public class _07_96_不同的二叉搜索树 {
    public static int numTrees(int n) {
    	int N = 30;
    	int dp[] = new int[N];
    	dp[0] = 1;
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= i; j++) {
    			dp[i] += dp[j-1] * dp[i-j]; 
    		}
    	}
    	
    	return dp[n];
    }
    public static void main(String[] args) {
    	System.out.println(numTrees(3));
	}
}
